1971E - Find the Car - CodeForces Solution

def bs(a, i):
    low = 0
    high = len(a) - 1
    res = -1
    while low <= high:
        mid = (low + high) // 2
        if a[mid]  <= i:
            low = mid + 1
            res = mid
        else:
            high = mid - 1
    return res

for _ in range(int(input())):
    n,k,q = [int(x) for x in input().split()]
    a = [0] + [int(x) for x in input().split()]
    b = [0] + [int(x) for x in input().split()]
    d = []
    for i in range(q):
        d.append(int(input()))
    res = []
    for i in d:
        x = bs(a, i)
        if a[x] == a[-1]:
            res.append(b[x])
        else:
            res.append((b[x] + (i-a[x]) * (b[x+1]- b[x]) // (a[x+1]- a[x])))
    print(*res)